#ifndef _SPLAY_H_
#define _SPLAY_H_

#include "MemoryPool.h"
#include <functional>
#include <stack>
#include <iostream>
using std::cout;
using std::endl;
using std::stack;
using std::pair;
using std::less;
using std::make_pair;
using std::unary_function;

#define POOL_SIZE 1000000

template <typename V, typename K>
struct DummyKeyExtractor;

template<typename K, typename V = K, typename Pr = less<K>, typename Ex = DummyKeyExtractor<V, K> >
class SplayTree {
	typedef K key_type;
	typedef V value_type;
public:
	class SplayNode {
		friend class SplayTree;
		SplayNode* _left;
		SplayNode* _right;
	public:
		value_type data;
		SplayNode(SplayNode* leftp = NULL, SplayNode* rightp = NULL): _left(leftp), _right(rightp) {}
		SplayNode(const value_type& dat, SplayNode* leftp = NULL, SplayNode* rightp = NULL): data(dat), _left(leftp), _right(rightp) {}
	};

	typedef MemoryPool<SplayNode, POOL_SIZE> pool_type;
private:
	static pool_type _pool;

public:
	static void destroyPool() {
		_pool.destroyPool();
	}

	SplayNode* newNode(SplayNode* leftp = NULL, SplayNode* rightp = NULL) {
		SplayNode* ret = _pool.newObject();
		ret->_left = leftp;
		ret->_right = rightp;
		return ret;
	}

	SplayNode* newNode(const value_type& datav, SplayNode* leftp = NULL, SplayNode* rightp = NULL) {
		void* ret = _pool.newPlacement();
		new(ret) SplayNode(datav, leftp, rightp);
		return (SplayNode*)ret;
	}

	void deleteNode(SplayNode* obj) {
		_pool.deleteObject(obj);
	}

	class iterator {
		friend class SplayTree;
		SplayNode* _cur;
		stack<SplayNode*> _dfsStk;
	public:
		iterator(): _cur(NULL) {}

		// algorithmic
		iterator& operator++() {
			SplayNode* curAccess;
			while (!_dfsStk.empty()) {
				curAccess = _dfsStk.top();
				if (_cur == curAccess->_left) {
					if (curAccess->_right != NULL) {
						_dfsStk.push(curAccess->_right);
					} else {
						_dfsStk.pop();
					}
					_cur = curAccess;
					return *this;
				} else if (_cur == curAccess->_right) {
					_dfsStk.pop();
					_cur = curAccess;
				} else {
					if (curAccess->_left != NULL) {
						_dfsStk.push(curAccess->_left);
					} else {
						_cur = NULL;
					}
				}
			} // while (!dfsStk.empty())
			_cur = NULL;
			return *this;
		}

		iterator operator++(int) {
			iterator tmp(*this); ++(*this); return tmp;
		}

		// happy dereferencer
		value_type& operator*() const {
			return _cur->data;
		}

		value_type* operator->() const {
			return &(_cur->data);
		}

		// compare
		bool operator==(const iterator& other) const {
			return _cur == other._cur;
		}

		bool operator!=(const iterator& other) const {
			return _cur != other._cur;
		}
	};

	class const_iterator {
		friend class SplayTree;
		SplayNode* _cur;
		stack<SplayNode*> _dfsStk;
	public:
		const_iterator(): _cur(NULL) {}
		const_iterator(const iterator& other) {
			_cur = other._cur;
			_dfsStk = other._dfsStk;
		}

		// algorithmic
		const_iterator& operator++() {
			SplayNode* curAccess;
			while (!_dfsStk.empty()) {
				curAccess = _dfsStk.top();
				if (_cur == curAccess->_left) {
					if (curAccess->_right != NULL) {
						_dfsStk.push(curAccess->_right);
					} else {
						_dfsStk.pop();
					}
					_cur = curAccess;
					return *this;
				} else if (_cur == curAccess->_right) {
					_dfsStk.pop();
					_cur = curAccess;
				} else {
					if (curAccess->_left != NULL) {
						_dfsStk.push(curAccess->_left);
					} else {
						_cur = NULL;
					}
				}
			} // while (!dfsStk.empty())
			_cur = NULL;
			return *this;
		}

		const_iterator operator++(int) {
			const_iterator tmp(*this); ++(*this); return tmp;
		}

		// happy dereferencer
		const value_type& operator*() const {
			return _cur->data;
		}

		value_type const* operator->() const {
			return &(_cur->data);
		}

		// compare
		bool operator==(const const_iterator& other) const {
			return _cur == other._cur;
		}

		bool operator!=(const const_iterator& other) const {
			return _cur != other._cur;
		}
	};

private:
	size_t m_size;
	SplayNode* m_root;
	Pr m_key_less;
	Ex m_key_extr;

	SplayNode* splay (const key_type& i, SplayNode* t) {
		/* Simple top down splay, not requiring i to be in the tree t.  */
		/* What it does is described above.                             */
		SplayNode N, *l, *r, *y;
		if (t == NULL) return t;
		l = r = &N;

		for (;;) {
			if ( m_key_less(i, m_key_extr(t->data)) ) {
				if (t->_left == NULL) break;
				if ( m_key_less(i, m_key_extr(t->_left->data)) ) {
					y = t->_left;                           /* rotate right */
					t->_left = y->_right;
					y->_right = t;
					t = y;
					if (t->_left == NULL) break;
				}
				r->_left = t;                               /* link right */
				r = t;
				t = t->_left;
			} else if ( m_key_less(m_key_extr(t->data), i) ) {
				if (t->_right == NULL) break;
				if ( m_key_less(m_key_extr(t->_right->data), i) ) {
					y = t->_right;                          /* rotate left */
					t->_right = y->_left;
					y->_left = t;
					t = y;
					if (t->_right == NULL) break;
				}
				l->_right = t;                              /* link left */
				l = t;
				t = t->_right;
			} else {
				break;
			}
		}
		l->_right = t->_left;                                /* assemble */
		r->_left = t->_right;
		t->_left = N._right;
		t->_right = N._left;
		return t;
	}

	pair<SplayNode*, bool> insert(const value_type& i, SplayNode* t) {
		/* Insert i into the tree t, unless it's already there.    */
		/* Return a pointer to the resulting tree.                 */
		SplayNode* nwNode = NULL;
		if (t == NULL) {
			nwNode = newNode(i, NULL, NULL);
			return make_pair(nwNode, true);
		}
		t = splay(m_key_extr(i),t);
		if ( m_key_less(m_key_extr(i), m_key_extr(t->data)) ) {
			nwNode = newNode(i, t->_left, t);
			t->_left = NULL;
			return make_pair(nwNode, true);
		} else if ( m_key_less(m_key_extr(t->data), m_key_extr(i)) ) {
			nwNode = newNode(i, t, t->_right);
			t->_right = NULL;
			return make_pair(nwNode, true);
		} else { /* We get here if it's already in the tree */
			/* Don't add it again                      */
			return make_pair(t, false);
		}
	}

	pair<SplayNode*, bool> erase(const key_type& i, SplayNode* t) {
		/* Deletes i from the tree if it's there.               */
		/* Return a pointer to the resulting tree.              */
		SplayNode* x;
		if (t==NULL) {
			return make_pair(NULL, false);
		}
		t = splay(m_key_extr(i),t);
		if ( !m_key_less(i, m_key_extr(t->data)) && !m_key_less(m_key_extr(t->data), i) ) {               /* found it */
			if (t->_left == NULL) {
				x = t->_right;
			} else {
				x = splay(m_key_extr(i), t->_left);
				x->_right = t->_right;
			}
			deleteNode(t);
			return make_pair(x, true);
		}
		return make_pair(t, false);                         /* It wasn't there */
	}

public:
	SplayTree(): m_root(0), m_size(0) {};

	virtual ~SplayTree() {}

	pair<iterator, bool> insert(const value_type& i) {
		pair<SplayNode*, bool> ret = insert(i, m_root);
		m_root = ret.first;
		if (ret.second) {
			++m_size;
		}
		iterator it;
		SplayNode*& cur = it._cur;
		stack<SplayNode*>& dfsStk = it._dfsStk;
		cur = ret.first;
		dfsStk.push(cur);
		if (cur->_right != NULL) {
			dfsStk.push(cur->_right);
		} else {
			dfsStk.pop();
		}
		return make_pair(it, ret.second);
	}

	bool erase(const key_type& i) {
		pair<SplayNode*, bool> ret = erase(i, m_root);
		m_root = ret.first;
		if (ret.second) {
			--m_size;
		}
		return ret.second;
	}

	SplayNode* splayFind(const key_type& i) {
		/* Deletes i from the tree if it's there.               */
		/* Return a pointer to the resulting tree.              */
		if (m_root==NULL) {
			return NULL;
		}
		m_root = splay(i, m_root);
		if ( !m_key_less(i, m_key_extr(m_root->data)) && !m_key_less(m_key_extr(m_root->data), i) ) {               /* found it */
			return m_root;
		}
		return NULL;
	}

	size_t splayCount(const key_type& i) {
		return (splayFind(i) ? 1 : 0);
	}

	const_iterator begin() const {
		const_iterator it;
		stack<SplayNode*>& dfsStk = it._dfsStk;
		SplayNode*& cur = it._cur;
		cur = m_root;
		while ( cur && cur->_left != NULL ) {
			dfsStk.push(cur);
			cur = cur->_left;
		} // while ( cur != NULL && (m_key_less(cur->data, i) || m_key_less(i, cur->data)) )
		if (cur != NULL) {
			dfsStk.push(cur);
			if (cur->_right != NULL) {
				dfsStk.push(cur->_right);
			} else {
				dfsStk.pop();
			}
		} else {
			return const_iterator();
		}
		return it;
	}

	iterator begin() {
		iterator it;
		stack<SplayNode*>& dfsStk = it._dfsStk;
		SplayNode*& cur = it._cur;
		cur = m_root;
		while ( cur && cur->_left != NULL ) {
			dfsStk.push(cur);
			cur = cur->_left;
		} // while ( cur != NULL && (m_key_less(cur->data, i) || m_key_less(i, cur->data)) )
		if (cur != NULL) {
			dfsStk.push(cur);
			if (cur->_right != NULL) {
				dfsStk.push(cur->_right);
			} else {
				dfsStk.pop();
			}
		} else {
			return iterator();
		}
		return it;
	}

	const_iterator end() const {
		return const_iterator();
	}

	iterator end() {
		return iterator();
	}

	iterator find(const key_type& i) {
		iterator it;
		stack<SplayNode*>& dfsStk = it._dfsStk;
		SplayNode*& cur = it._cur;
		cur = m_root;
		while ( cur != NULL && (m_key_less(m_key_extr(cur->data), i) || m_key_less(i, m_key_extr(cur->data))) ) {
			dfsStk.push(cur);
			if (m_key_less(i, m_key_extr(cur->data))) {
				cur = cur->_left;
			} else {
				cur = cur->_right;
			}
		} // while ( cur != NULL && (m_key_less(cur->data, i) || m_key_less(i, cur->data)) )
		if (cur != NULL) {
			dfsStk.push(cur);
			if (cur->_right != NULL) {
				dfsStk.push(cur->_right);
			} else {
				dfsStk.pop();
			}
		} else {
			return iterator();
		}
		return it;
	}

	size_t count(const key_type& i) const {
		return (find(i) == end() ? 0 : 1);
	}

	void order() const {
		SplayNode* lastAccessed = m_root;
		SplayNode* curAccess = m_root;
		stack<SplayNode*> dfsStk;
		dfsStk.push(m_root);
		while (!dfsStk.empty()) {
			curAccess = dfsStk.top();
			if (lastAccessed == curAccess->_left) {
				cout << curAccess->data <<endl;
				if (curAccess->_right != NULL) {
					dfsStk.push(curAccess->_right);
				} else {
					dfsStk.pop();
				}
				lastAccessed = curAccess;
			} else if (lastAccessed == curAccess->_right) {
				dfsStk.pop();
				lastAccessed = curAccess;
			} else {
				if (curAccess->_left != NULL) {
					dfsStk.push(curAccess->_left);
				} else {
					lastAccessed = NULL;
				}
			}
		} // while (!dfsStk.empty())
	}

	size_t size() const {
		return m_size;
	}

	bool empty() const {
		return !m_size;
	}

	void clear() {
		SplayNode* lastAccessed = m_root;
		SplayNode* curAccess = m_root;
		stack<SplayNode*> dfsStk;
		dfsStk.push(m_root);
		while (!dfsStk.empty()) {
			curAccess = dfsStk.top();
			if (lastAccessed == curAccess->_left) {
				if (curAccess->_right != NULL) {
					dfsStk.push(curAccess->_right);
				} else {
					deleteNode(curAccess);
					dfsStk.pop();
				}
				lastAccessed = curAccess;
			} else if (lastAccessed == curAccess->_right) {
				deleteNode(curAccess);
				dfsStk.pop();
				lastAccessed = curAccess;
			} else {
				if (curAccess->_left != NULL) {
					dfsStk.push(curAccess->_left);
				} else {
					lastAccessed = NULL;
				}
			}
		} // while (!dfsStk.empty())

		m_root = 0;
		m_size = 0;
	}
};

#endif